package com.clstu.leetcode;

import com.clstu.stack.Calculator;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * leetCode剑指offer 41,中位数
 */
class MedianFinder {

    public static void main(String[] args) {
        //测试
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.addNum(3);
        System.out.println(medianFinder.minHeap);
        System.out.println(medianFinder.maxHeap);
    }

    //准备两个堆,一个小根堆,一个大根堆,控制两个堆的size()相差不超过1,中位数就是小根堆堆顶或者大根堆堆顶或者他们的中位数
    public PriorityQueue<Integer> minHeap ;
    public PriorityQueue<Integer> maxHeap ;
    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue<>(new MinComparator());
        maxHeap = new PriorityQueue<>(new MaxComparator());
    }

    public void addNum(int num) {
        //如果有堆为空
        if(maxHeap.isEmpty()){
            maxHeap.add(num);
            return;
        }
        if(num>maxHeap.peek()){
            minHeap.add(num);
        }else {
            maxHeap.add(num);
        }
        //调整
        if(minHeap.size() - maxHeap.size() > 1){
            maxHeap.add(minHeap.poll());
        }
        if(maxHeap.size() - minHeap.size() > 1){
            minHeap.add(maxHeap.poll());
        }
    }

    public double findMedian() {
        if(minHeap.size()>maxHeap.size()){
            return minHeap.peek();
        }
        if(maxHeap.size()>minHeap.size()){
            return maxHeap.peek();
        }
        return (minHeap.peek()+maxHeap.peek())/2.0;
    }

    //比较器,小在前
    public static class MinComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }

    //比较器,大在前
    public static class MaxComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
